The present invention relates to halftone screening in general and, more particularly to electronic halftoning for the reproduction of tints and images on, for example, offset printing presses.
Offset presses behave like binary devices, in that they can only print "ink" or "no ink" at a given location of the substrate, rather than being capable of locally modulating the thickness or concentration of the ink. In order to render different tones and colors, necessary for the reproduction of images and tints, geometrical patterns are used of dots, of which the size is modulated. This process is called halftoning, and the dots that make up the pattern are called "halftone dots". The pitch of the dot pattern is fine enough not to be objectionable to the eye. Instead, the eye will perceive the "integrated density" that corresponds to the average coverage of the substrate with ink.
For digital halftoning high resolution laser recorders are used to generate halftone dots on a photographic film or plate. The laser beam scans the film or plate on a line-by-line basis. Within every line the laser beam can be modulated "on" or "off" at discrete positions. In this way, an addressable grid is formed of lines and columns. The smallest addressable unit of this grid can conveniently be called a "micro dot" (as opposed to the word "dot" which is reserved to refer to the halftone dots themselves). The pitch of the grid is usually the same in the horizontal and vertical directions, and lies in the range from 0.25 to 1.00 thousands of an inch, corresponding to recorder resolutions of 4000 to 1000 micro dots/inch, respectively. Halftone dots are then built by turning the laser on and off in such a way that contiguous clusters of micro dots are written on the addressable grid, the size of which corresponds to the desired local tone level. FIG. 1 depicts how the different shades of a degrade are rendered by means of digital halftone dots with different sizes.
The generation of a halftone dot pattern on a fixed resolution grid involves a number of trade-offs. The fact that the dots are "built" by clustering micro dots, results in spatial discretization effects. These effects can be classified into three categories:
1) Discretization of the possible SIZES of the dots. The size difference between two dots corresponds always to an integer number of micro dots.
2) Discretization of the microscopic SHAPE of the dots. Since the micro dots that make up the dot boundary are positioned on an orthogonal grid, the dot boundaries will always be a "serrated version" of what the mathematical dot boundary description predicts.
3) Discretization of the dot POSITION. The gravity center of a cluster of micro dots that makes up a halftone dot does not necessarily coincide exactly with the location of the dot centers as predicted by the mathematical halftone description.
The following discussion concentrates on the two latter problems: discretization of dot SHAPE and POSITION.
Although the serration itself of the dot shape is usually invisible, it can indirectly affect the size of the halftone dot as it will appear after exposure and development of the film. The causes for this are complex and involve non-linearities and asymmetries in the film/recorder system. This can be demonstrated by a simplified example.
FIG. 2a illustrates how the energy of a scanning laser beam in an image recorder rises and falls in time when an optical modulator turns it "on" and "off". Also indicated is the "developly level" of energy at which the exposed film will start to become black when it is developed. It is assumed in FIG. 2a that the scanning laser beam has the shape of a line, perpendicularly oriented to the scanning direction and a length equal to the distance between two successive scanning lines. FIGS. 2b and 2d indicate how long the the black lines would be on the film if the modulator turns on the laser beam during one micro dot (FIG. 2b) and during two mocro dots (FIG. 2d). FIGS. 2c and 2e depict the black area that would result on the film for a halftone dot formed of two (2) vertically and two (2) horizontally oriented micro dots. It can be seen from the Figures that both halftone dots are imaged with DIFFERENT SIZES on the film.
If a halftone dot pattern is generated in which these two kinds of halftone dots occur in groups, as for example in FIG. 3, an objectionable low frequency periodical DENSITY pattern will be introduced caused by the difference in size between the dots that are imaged larger and smaller because of the film/recorder characteristics.
Since, as just explained, the dot boundaries of halftone dots on film are approximations of what their mathematical description would predict, it is to be expected that this will affect the location of the gravity center of the halftone dots. FIG. 4 illustrates how the "theoretical" and "actually" center of gravity of halftone dots can differ for a halftone dot of two horizontally oriented micro dots and two vertically oriented micro dots. The inconsistency between the theoretical and actual dot centers can be viwed as a local "phase distortion" of the created versus the theoretical halftone dot screen. Another way of looking at this periodical phase distortion is to consider it as a moire interaction between the frequencies of the halftone screen and the recorder grid.
The coordinates (xa,ya) of the actual center of gravity of a halftone dot consisting of N micro dots is given by: ##EQU1## From this formula it can be seen that the actual center of gravity can better approximate the theoretical center of gravity if the halftone dot is formed from of large numbers of micro dots. Given the presence of N in the nominator, the "corrections" to converge both can be made smaller if N is large.
Phase distortions in halftone screens can be quite visible to the eye. If they are random (in angle and amplitude), they make the halftone screen look "noisy" or grainy. If they are periodical, they introduce "patterning" as shown in FIG. 3. On most rows and columns, a series of "horizontal" and "vertical" dots alternate, which introduces a periodical phase distortion of the halftone screen in both dimensions. Since the period of this phase distortion is much longer than the period of the halftone screen itself, it will be visible when looked at under normal scaling conditions.
Several techniques have been described in the patent literature to break up the patterning that results from these periodical shape and phase variations. The three most representative cases are all based on the introduction of a random element to "break up" the periodicity of the shape and phase variations.
FIG. 5 depicts the essential parts of a halftone screen generator as it is described by Rosenfeld (in U.S. Pat No. 4,350,996 and U.S. Pat. No. 4,456,924) and by Gall (in U.S. Pat. No. 4,499,489 and U.S. Pat. No. 4,700,235). At the recorder grid position (i,j) with physical coordinates values Ui and Vj, the value of the pixel that is to be half-toned is P(i,j). The position coordinate pair (Ui,Vj) of the recorder is, by means of a coordinate transformation unit (designed to scale, rotate and shift coordinate pairs), converted into the screen position coordinate pair (Xi',Yj'). Based on the fact that the screen function is periodical, a sampled version of only one screen function period is stored in a MxM matrix memory. Therefore, the screen position coordinates Xi' and Yj' are mapped, by means of a modulo M operation into coordinate values (Xi,Yj) of that one period. The coordinates (Xi,Yj) address a threshold value T(i,j), which is then compared with the original pixel value P(i,j). Depending on the outcome of this comparison, a "black" or "white" micro dot will be written by the recorder on the screen. A variation on this technique, in which the "thresholding mechanism" is replaced by precalculated "bitmap caches", is described by Granger in U.S. Pat. No. 4,918,622.
There are several ways to introduce a random element to break phase deviation periodicity. In one method , two numbers Xn, and Yn, generated by a random generator and uniformly distributed within a certain range, are added to the screen coordinate values Xi' and Yi'. This will vary the location of the halftone dot boundary in a probabilistic manner, and spread the energy of the periodic phase deviation across an address band surrounding the halftone dot boundary. FIG. 6 illustrates this method, which is also explained in U.S. Pat. No. 4,499,489 and U.S. Pat. No. 4,918,622.
In FIG. 6a, the black square indicates the "theoretical" boundary of a halftone dot. The black circles show how this area is approximated by a cluster of micro dots. As is seen in the Figure, the "actual" center of gravity of the cluster of micro dots does not coincide with the theoretical center thereby introducing a phase error. FIG. 6b illustrates the situation in which random numbers, uniformly distributed between -0.5 and +0.5 times the recorder pitch, are added to the position coordinates of the theoretical dot boundary. This range is indicated in FIG. 6b by the inner and outer squares. The "gray" circles represent micro dots that are assigned OR not assigned to the halftone dot in a probabilistic manner. The outcome of this process, for example, can be the one that is shown in FIG. 6c. The total number of micro dots is the same, but the location of the "actual" center of gravity is much nearer to the "theoretical" one.
A second method, described in U.S. Pat. No. 4,700,235 makes use of not one, but several memories each containing a prestored halftone period. The phase of these prestored periods is set slightly different. A random generator on FIG. 5 produces numbers "Sn" that determine WHICH of the available prestored screen periods is sampled to obtain a threshold value. The net result of this operation is comparable to what was described in the first method.
A third method, described in U.S. Pat. No. 4,456,924, simply consists of adding random numbers "Tn" with a certain range to the threshold values that result from sampling of the screen period. This method has no effect on the phase of the resulting cluster of micro dots, but it is capable of "masking" the low frequency patterning that results from the periodical phase deviations.
All of the above methods have the disadvantage that they produce irregularly shaped dot boundaries, especially if the screens are generated at low recorder resolutions. For example, with a 133 lines per inch screen at a resolution of 1200 micro dots per inch), the microscopic quality of the dot shapes is quite unacceptable. Not only is the serration of such halftone dots displeasing when looked at under a microscope, it is also the source of additional "dot gain" when such a screen is printed on a press, since press gain is closely related to the halftone dot circumference. The irregularity of the dot boundary also leads to dot-to-dot differences in press gain, resulting in an increase of the overall noise level of the reproduced image.